HW#5 --- last modified February 28 2019 23:10:45..

Solution set.

Due date: May 14

Files to be submitted:
  Hw5.zip

Purpose: To learn about turing machines and other general models of computation. To understand uncomputability and in particular the halting problem.

Related Course Outcomes:

(9) Construct a Turing machine accepting some simple languages.

(10)State in precise mathematical terms what is meant by undecidability of the Halting Problem, and be able to show the undecidability of simple extensions of the Halting Problem, using the reduction technique.

Specification:

You should include all files for this assignment in Hw5.zip. For the first partof the assignment, each group member should indivdually go to http://www.surveymonkey.com/s.asp?u=174663544296 and do the second JFLAP survey (get screenshots of each page). Remember at the end of the survey you can choose not to participate in the study if you do not want to; I am only interested in the screenshots of the computer science related questions.

After doing the survey, design using JFLAP a Turing Machine which when given aⁿ on its tape computes a^n! and halts. Submit this as part of your ZIP file under the name nfac.jff.

Finally, do the following problems out of our of book and submit them in the file Hw5.pdf, which you should include as well in Hw5.zip: p257 #10, p266 #5, p305 #5, p319 #5.

Point Breakdown